public class RevisedSimplex {

    private static final double inf = 1e9;

    private int n;							// 约束个数
    private double[][] A;					// 输入函数參数
    private double[] b;					// 约束值
    private double[] c;					// 目标函数系数
    private double Z;						// 目标值
    private void InitF() {					// 初始化 First
        /* problem 1.
         * max Z = 5*x1 + 4*x2;			  min Z = -5*x1 - 4*x2;
         * x1   + 3*x2 <= 90;				x1 + 3*x2 +  x3				= 90;
         * 2*x1 + x2   <= 80;		=>	  2*x1 +   x2 	    + x4		= 80;
         * x1   + x2   <= 45;				x1 +   x2   		  + x5 	= 45;
         * xi >= 0
         */
        /* problem 2.
         * min Z = -7*x1 - 12*x2;
         * 9*x1 + 4*x2  + x3          = 360;
         * 4*x1 + 5*x2       +x4 	  = 200;
         * 3*x1 + 10*x2			 + x5 = 300;
         *   xi >= 0
         */
        n = 3;
        A = new double[n+1][n+1];
        b = new double[n+1];
//		c = new double[n<<1];
        Z = inf;
        // 约束初始条件
        A[1][1] = 1;	A[1][2] = 3;
        A[2][1] = 2;	A[2][2] = 1;
        A[3][1] = 1;	A[3][2] = 1;
        // 条件值
        // problem 1.
//		b[1] = 90;
//		b[2] = 80;
//		b[3] = 45;
        // problem 2.
        b[1] = 360;
        b[2] = 200;
        b[3] = 300;
//		for(int i = 1; i <= n; i++)System.out.println("b[" + i + "] = " + b[i]);
        // 目标函数系数
//		c[1] = -5;	c[2] = -4;
    }

    int m;
    private double[][] p;
    private double[][] e, oe;
    private double[][] E, oE;
    private double[] X;
    private boolean[] G;
    private int[] S;
    private void InitS() {
        m = 2;
        p = new double[n+1][n+m+1];
        e = new double[n+1][n+1];
        oe = new double[n+1][n+1];
        E = new double[n+1][n+1];
        oE = new double[n+1][n+1];
        X = new double[n+1];
        G = new boolean[n+m+1];
        S = new int[n+1];

        c = new double[n+m+1];
        // problem 1.
//		c[1] = -5;	c[2] = -4;	c[3] = 0;	c[4] = 0;	c[5] = 0;
        // problem 2.
        c[1] = -7;	c[2] = -12;	c[3] = 0;	c[4] = 0;	c[5] = 0;
        // problem 1.
//		p[1][1] = 1;	p[1][2] = 3;	p[1][3] = 1;	p[1][4] = 0;	p[1][5] = 0;
//		p[2][1] = 2;	p[2][2] = 1;	p[2][3] = 0;	p[2][4] = 1;	p[2][5] = 0;
//		p[3][1] = 1;	p[3][2] = 1;	p[3][3] = 0;	p[3][4] = 0;	p[3][5] = 1;
        // problem 2.
        p[1][1] = 9;	p[1][2] = 4;	p[1][3] = 1;	p[1][4] = 0;	p[1][5] = 0;
        p[2][1] = 4;	p[2][2] = 5;	p[2][3] = 0;	p[2][4] = 1;	p[2][5] = 0;
        p[3][1] = 3;	p[3][2] = 10;	p[3][3] = 0;	p[3][4] = 0;	p[3][5] = 1;

        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                if(i == j)E[i][j] = oE[i][j] = 1;
                else E[i][j] = oE[i][j] = 0;

        for(int i = 1; i <= n; i++)
            X[i] = b[i];

        G[1] = false;	G[2] = false;	G[3] = true;	G[4] = true;	G[5] = true;

        S[1] = 3;	S[2] = 4;	S[3] = 5;
    }


    public RevisedSimplex() {
        InitF();
        InitS();
        AlgorithmProcess();
        solve();
    }

    private void AlgorithmProcess() {
        double[] coE = new double[n+1];	// c * E^-1
        double[] r = new double [n+m+1];	// c - c * E^-1 * p
        double[] oEp = new double[n+1];	// E^-1 * p;
        boolean flag = false;
        while(true) {
            // x = E^-1 * b
            for(int i = 1; i <= n; i++){
                X[i] = 0;
                for(int j = 1; j <= n; j++)
                    X[i] += oE[i][j]*b[j];
            }
            // c * E^-1
            for(int i = 1; i <= n; i++){
                coE[i] = 0;
                for(int j = 1; j <= n; j++)
                    coE[i] += c[S[j]]*oE[j][i];
            }
            // r = c - c * E^-1 * p     => min r' id -> k
            int k = -1;
            flag = false;
            for(int i = 1; i <= n+m; i++)if(!G[i]){
                double ans = 0;
                for(int j = 1; j <= n; j++)
                    ans += coE[j]*p[j][i];
                r[i] = c[i] - ans;
                if(!flag && r[i] < 0){
                    k = i;
                    flag = true;
                }else if(flag && r[i] < r[k]){
                    k = i;
                }
            }
            if(k == -1)return ;									// solution output 1（X, S 为最优解）
            // E^-1 * p;				=> min theta>0' id -> s
            int s = -1;
            flag = false;
            for(int i = 1; i <= n; i++){
                oEp[i] = 0;
                for(int j = 1; j <= n; j++){
                    oEp[i] += oE[i][j]*p[j][k];
                }
                if(oEp[i] > 0){
                    if(!flag){
                        s = i;
                        flag = true;
                    }else if(flag && X[i]/oEp[i] < X[s]/oEp[s]){
                        s = i;
                    }
                }
            }
            if(!flag)return ; 										// no solution 1（无同意解）
            if(s == -1)return ;									// no solution 2（该问题有无解集）
            // p[s] = p[k], 形成新的矢量基 E
            G[S[s]] = false;	G[k] = true;
            S[s] = k;
//			System.out.println("k = " + k + "; s = " + s);
            for(int i = 1; i <= n; i++){
                p[i][k] = -1.0*oEp[i]/oEp[s];
                if(i == s)
                    p[i][k] = 1/oEp[s];
            }
            for(int i = 1; i <= n; i++){
                int id = S[i];
                for(int j = 1; j <= n; j++){
                    if(i == s){
                        e[j][i] = p[j][k];
                    }else{
                        if(j == i){
                            e[j][i] = 1;
                        }else{
                            e[j][i] = 0;
                        }
                    }
                }
            }
//			for(int i = 1; i <= n; i++){
//				for(int j = 1; j <= n; j++){
//					System.out.print(oE[i][j] + " ");
//				}System.out.println();
//			}System.out.println("{oE}");
//			for(int i = 1; i <= n; i++){
//				for(int j = 1; j <= n; j++){
//					System.out.print(e[i][j] + " ");
//				}System.out.println();
//			}System.out.println("{e}");
            for(int i = 1; i <= n; i++){
                for(int j = 1; j <= n; j++){
                    oe[i][j] = 0;
                    for(int t = 1; t <= n; t++){
                        oe[i][j] += e[i][t]*oE[t][j];
                    }
                }
            }
            for(int i = 1; i <= n; i++){
                for(int j = 1; j <= n; j++){
                    oE[i][j] = oe[i][j];
                    //System.out.print(oE[i][j] + " ");
                }//System.out.println();
            }//System.out.println();
        }
    }
    // 最优解输出
    private void solve() {
        Z = 0;
        for(int i = 1; i <= n; i++){
            int id = S[i];
            Z += c[id]*X[i];
            System.out.println(id + " : " + X[i] + " * " + -c[id]);
        }
        System.out.println("Z = " + -Z);
    }

    public static void main(String[] args) {
        new RevisedSimplex();
    }
}
